import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树的创建
 */
public class BinaryTree {

    //创建一个节点类
    static class TreeNode{
        //左右孩子节点
        TreeNode left;//左孩子
        TreeNode right;//右孩子

        //存放值
        int val;

        public TreeNode(int val){
            this.val = val;
        }
    }

    //根节点
    private TreeNode root;

    //创建根节点
    public  TreeNode createBinaryTree(int[] values){
        int len = values.length;
        //空数组
        if(len == 0) return null;
        //只有一个元素
        if(len == 1) {
            root.val = values[0];
            return root;
        }
        //多个元素
        Queue<TreeNode> q = new LinkedList<>();
        root = new TreeNode(values[0]);
        q.offer(root);
        int i = 1;
        while(!q.isEmpty() && i < len) {
            int size = q.size();
            while(size-- != 0){
                TreeNode cur = q.poll();
                if(i < len)
                {cur.left = new TreeNode(values[i++]);
                q.offer(cur.left);}
                if(i < len)
                {cur.right = new TreeNode(values[i++]);
                q.offer(cur.right);}
            }
        }
        return root;
    }

    //层序遍历
    public void levelOrder(){

        //1.创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        //将根节点加入队列
        queue.offer(root);
        //2.第一层循环
        int i = 1;
        while(!queue.isEmpty()){
            //3.第二层循环
            int size = queue.size();
            System.out.print("第" + i  + "层节点值：");
            while(size-- != 0){
                //弹出节点
                TreeNode tem = queue.poll();
                //打印
                System.out.print(tem.val + " ");
                //左右节点加入队列,不为空才加入
                if(tem.left != null)
                 queue.offer(tem.left);
                if(tem.right != null)
                 queue.offer(tem.right);
            }
            i++;
            System.out.println();
        }
    }

    private void preOrder(TreeNode root){
        //递归结束条件
        if(root == null) return;
        //按照根左右递归
        System.out.print(root.val + " ");

        preOrder(root.left);

        preOrder(root.right);
    }
    //前序遍历
    public void preOrder(){
        if(root == null) return;

        //封装一层函数
        preOrder(root);
     }

    private void inOrder(TreeNode root){
        //递归结束条件
        if(root == null) return;
        //按照左根右递归
        inOrder(root.left);

        System.out.print(root.val + " ");

        inOrder(root.right);
    }
    //前序遍历
    public void inOrder(){
        if(root == null) return;

        //封装一层函数
        inOrder(root);
    }

    private void postOrder(TreeNode root){
        //递归结束条件
        if(root == null) return;
        //按照左右根递归
        postOrder(root.left);

        postOrder(root.right);

        System.out.print(root.val + " ");
    }
    //前序遍历
    public void postOrder(){
        if(root == null) return;

        //封装一层函数
        postOrder(root);
    }

    public int size(){
        int size = 0;
        if(root == null) return size;
        //1.创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        //将根节点加入队列
        queue.offer(root);
        size++;
        //2.第一层循环

        while(!queue.isEmpty()){
            //3.第二层循环
            int size1 = queue.size();
            while(size1-- != 0) {
                //弹出节点
                TreeNode tem = queue.poll();

                if (tem.left != null) {
                    queue.offer(tem.left);
                    size++;
                }
                if (tem.right != null){
                    queue.offer(tem.right);
                    size++;
                }
            }
        }
        return size;
    }
    //获取叶子节点个数：递归解决
    private int getLeafNodeCount(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;

        return  getLeafNodeCount(root.left) + getLeafNodeCount(root.right);

    }
    public int getLeftNodeCount(){
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;

        //封装一层
        return getLeafNodeCount(root);
    }

    //获取第k层节点个数:递归获取第k层左子树或右子树的节点数目
    public int getKLevelNodeCount(TreeNode root ,int k){
        if(root == null) return 0;
        if(k == 1) return 1;
        return getKLevelNodeCount(root.right,k -1) + getKLevelNodeCount(root.left, k -1);
    }
    public int getKLevelNodeCount(int k){
        return getKLevelNodeCount(root,k);
    }

    private int getHeight(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right == null) return 1;

        return 1 + Math.max(getHeight(root.left),getHeight(root.right));
    }
    //求二叉树的深度
    public int getHeight(){
        return getHeight(root);
    }

    //查找元素
    public TreeNode findElement(TreeNode root,int val) {

        if(root == null) return null;
        if(root.val == val) return root;

        TreeNode left = findElement(root.left,val);
        if(left != null) return left;
        TreeNode right = findElement(root.right,val);
        if(right != null) return right;

        return null;
    }
    public TreeNode findElement(int val) {
        return findElement(root,val);
    }


    public boolean isCompleteBinaryTree3(TreeNode root){
        //空树是完全二叉树
        if(root == null) return true;

        if(root.left == null && root.right == null) return true;

        //1.使用队列，加入根节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur;
        //队列中不存在null的节点
        boolean flat = false;

        //2.第一层循环
        while(!queue.isEmpty()){
            cur = queue.poll();
            if(cur == null){
               flat = true;
               continue;
            }
            //队列中存在null，后面不能存在不为null的节点
            if(flat && cur != null){
                return false;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }

        return true;
    }
    public boolean isCompleteBinaryTree2(TreeNode root){

        if(root == null) return true;
        //默认没有度不为2的节点
        boolean flat = false;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){

            TreeNode cur = queue.poll();

            //有右孩子，没左孩子，不是完全二叉树
            if(root.left == null && root.right != null){
                return false;
            }

            //度不为二的节点，进行标记
            if(flat && cur.left != null){
                return false;
            }

            if(cur.left == null || cur.right == null){
                flat = true;
            }

            //左右孩子不为空入队列
            if(cur.left != null) queue.offer(cur.left);

            if(cur.right != null) queue.offer((cur.right));

        }
        //以上情况都没有返回，说明是完全二叉树
        return true;
    }

    public boolean isCompleteBinaryTree1(TreeNode root){
        //空树是完全二叉树
        if(root == null) return true;

        if(root.left == null && root.right == null) return true;

        //1.使用队列，加入根节点
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode cur = root;

        //2.第一层循环
        while(null != cur){
            int size = queue.size();
            //第二层循环
            while(size-- != 0){
                cur = queue.poll();
                if(cur != null) {
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }
            }
        }

        //3.将队列元素全部弹出
        while(!queue.isEmpty()){
            if(queue.poll() != null)
                return false;
        }
        return true;
    }

    public static void main(String[] args) {
        TreeNode node1 =new TreeNode(1);
        TreeNode node2 =new TreeNode(1);
        TreeNode node3 =new TreeNode(1);
        TreeNode node4 =new TreeNode(1);
//        node1.left = node2;
//        node2.left = node3;
//        node3.left = node4;

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;

        BinaryTree b = new BinaryTree();
        System.out.println(b.isCompleteBinaryTree2(node1));
    }


    public static void main4(String[] args) {
        BinaryTree b = new BinaryTree();
        b.createBinaryTree(new int[]{1,2,3,4,5,6,7});
        //System.out.println(b.findElement(7).val);
        System.out.println("第二层节点数：" + b.getKLevelNodeCount(2));
    }
    public static void main3(String[] args) {
        BinaryTree b = new BinaryTree();
        b.createBinaryTree(new int[]{1,2,3,4});
//        System.out.println("二叉树的节点个数为：" + b.size());
//        System.out.println("二叉树叶子节点个数："+ b.getLeftNodeCount());
        System.out.println("二叉树的高度：" + b.getHeight());
    }
    public static void main1(String[] args) {
        BinaryTree b = new BinaryTree();
        TreeNode r = b.createBinaryTree(new int[]{1,2,3,4,5,6,7});
        // b.levelOrder();
        // System.out.println("=================");
        System.out.print("前序遍历：");
        b.preOrder();
        System.out.println();
        System.out.println("======================");
        System.out.print("中序遍历：");
        b.inOrder();
        System.out.println();
        System.out.println("======================");
        System.out.print("后序遍历：");
        b.postOrder();
        System.out.println();
    }
}


